Recent years have seen explosive growth of network-connected devices. Once limited to just personal computers and servers, now network connectivity is supported by doors and door locks, digital signage, network-enabled kiosks (e.g., parking meters, vending machines), and so on. Many of these devices interact with a user by way of the user's client device (e.g., a smartphone) so that the devices can perform tasks on behalf of the user. Given that billions of low-cost network-connected devices are expected to be deployed in the future, it is desirable to be able to provide secure and private mechanisms with which a client device can interact with these devices.